#include "config.h"
#include "cache.h"
#include "queue.h"

Memory::Memory(int _L2_count, int _min_L2_id, int _id) {
  L2_count = _L2_count;
  min_L2_id = _min_L2_id;
  L2Q = new Queue* [L2_count];
  Q = new Queue(_min_L2_id+_L2_count+1, _min_L2_id);
  id = _id;
  rsp_count = 0;
}

void Memory::SetL2(int _L2_id, Queue* _L2Q) {
  L2Q[_L2_id-min_L2_id] = _L2Q;
}

void Memory::Update() {
  // memory can commit any number of requests at a single cycle
  Q->Commit_Reqs(9999999);
  Q->Countdown();
  vector<QueueElement>::iterator it;
  while(Q->aq.size() !=0)
    Q->aq.pop_back();
  for(it=Q->oq.begin(); it!=Q->oq.end();) {
    if(it->cmd != WB) {
      assert(it->cmd == R || it->cmd == W);
      rsp_count++;
      L2Q[it->L2src-min_L2_id]->aq.push_back(*it);
    }
    it = Q->oq.erase(it);
  }
  if (Q->oq.size() != 0) {
    cout<<Q->oq.size()<<endl;
    assert(0);
  }
}

L2Cache::L2Cache(int _size, int _block_size, int _latency, 
      int _way, int _banks, int _id, int _minL1, int _maxL1) {
  bank_count = _banks;
  banks = new Cache*[_banks];
  for(int i=0; i<_banks; i++)
    banks[i] = new Cache(_size, _block_size, _latency, _way, _id);
  Q = new Queue(_maxL1, _minL1);
  L1Q = new Queue*[_banks];
  minL1 = _minL1;
  hit = 0;
  miss = 0;
  wb = 0;
  total = 0;
  inclusion_evict = 0;
  mem_req = 0;
  mem_rsp = 0;
}

bool L2Cache::QEmpty() {
  return waitQ.empty() && Q->Empty();
}

/*
void L2Cache::PrintStats() {
  cout<<"=================================================="<<endl;
  cout<<"L2 ID: "<<banks[0]->id<<endl;
  cout<<"\t Size: "<<banks[0]->size<<" KB\n";
  cout<<"\t BlockSize: "<<banks[0]->block_size<<" B\n";
  cout<<"\t Number of Blocks: "<<banks[0]->block_num<<endl;
  cout<<"\t Number of Sets: "<<banks[0]->way<<endl;
  cout<<"\t WriteBack Polic: WriteBack\n";
  cout<<"\t Latency: "<<L2_LATENCY<<"\n";
  cout<<"\t Hit: "<<hit<<endl;
  cout<<"\t Miss: "<<miss<<endl;
  cout<<"\t Write_back: "<<wb<<endl;
  cout<<"\t Total: "<<total<<endl;
  cout<<"\t Inclusion evict: "<<inclusion_evict<<endl;
  cout<<"\t Mem req: "<<mem_req<<endl;
  cout<<"\t Mem rsp: "<<mem_rsp<<endl;
}
*/

void L2Cache::PrintStats() {
  double ttl=hit+miss;

  cout.setf(ios::fixed, ios::floatfield);
  cout.setf(ios::showpoint);
  cout.precision(4);

  cout<<"L2: "<<'\t'<<(hit+miss)<<'\t'<<miss<<'\t'<<(miss/ttl)<<endl;
}

int L2Cache::GetBank(unsigned long addr) {
  unsigned int tag = banks[0]->GetTag(addr);
  return tag%bank_count;
}

bool L2Cache::FreshReqHandle(unsigned long addr, int requester, Cmd cmd) {
  unsigned int bank = GetBank(addr);
  if (cmd == R)
    return banks[bank]->Read(addr, requester);
  else if (cmd == W || cmd == WB)
    return banks[bank]->Write(addr, requester);
  else {
    assert(0);
    exit(1);
  }
}
// need to check coalascing inv requests before eviction

void L2Cache::MissReqHandle(unsigned long addr, int requester, Cmd cmd) {
  unsigned int bank = GetBank(addr);
  Block* new_block = banks[bank]->GetVictim(addr);
  // need to force inclusion
  if (new_block->valid) {
    while(!new_block->evict_list.empty()) {
      //if (new_block->dirty) {
      if (new_block->evict_list.front()->dirty) {
        wb++;
        // this request will just bypass L2 and goes to memory
        Q->NewReq(new_block->owner, new_block->addr, L2_LATENCY, 99, WB);
      }
      new_block->evict_list.front()->valid = 0;
      new_block->evict_list.pop_front();
      inclusion_evict++;
    }
  }
  // if victim is dirty, needs to writeback
  if (new_block->valid && new_block->dirty) {
    wb++;
    MemQ->NewReq(new_block->owner, new_block->addr, MEM_LATENCY, banks[0]->id, WB);
    new_block->dirty = 0;
  }
  // fill new_block with new data
  banks[bank]->FillBlock(addr, cmd, requester, new_block);
}

void L2Cache::CoalascingHandle(unsigned long addr, int requester) {
  vector<QueueElement>::iterator it;
  for(it = waitQ.begin(); it != waitQ.end();) {
    if(requester==it->src && banks[0]->SameTagIndex(addr, it->addr)) {
      bool r = FreshReqHandle(addr, requester, it->cmd);
      assert(r == true);
      if (it->cmd != WB)
        L1Q[it->src-minL1]->aq.push_back(*it);
      it = waitQ.erase(it);
      if (it == waitQ.end())
        break;
    }
    else
      it++;
  }
  return;
}

void L2Cache::Update() {
  // take new request and count down
  Q->Commit_Reqs();
  Q->Countdown();
  // update outstanding request using rsp
  vector<QueueElement>::iterator it;
  bool aq_handled;
  while(Q->aq.size() != 0) {
    aq_handled = 0;
    // detach an L1 block from L2
    if(Q->aq.back().cmd == EVICT) {
      unsigned int bank = GetBank(Q->aq.back().addr);
      Block* blk = banks[bank]->findBlock(Q->aq.back().addr, Q->aq.back().src);
      //assert(blk != NULL);
      // cannot make this assertion because this block may have already been
      // evicted by an earlier request, in this case, inclusion is still promised
      // to avoid this, need another higher priority queue
      if (blk != NULL) {
        for(list<Block*>::iterator it = blk->evict_list.begin();
              it != blk->evict_list.end(); it++) {
          if (*it == Q->aq.back().blk) {
            blk->evict_list.erase(it);
            break;
          }
        }
      }
      aq_handled = 1;
      Q->aq.pop_back();
    }
    // attach an L1 block from L2
    else if(Q->aq.back().cmd == FILL) {
      unsigned int bank = GetBank(Q->aq.back().addr);
      Block* blk = banks[bank]->findBlock(Q->aq.back().addr, Q->aq.back().src);
      //assert(blk != NULL);
      if (blk != NULL)
        blk->evict_list.push_back(Q->aq.back().blk);
      Q->aq.pop_back();
      aq_handled = 1;
    }
    // response from memory
    else {
      unsigned long mis_addr;
      int mis_src;
      for(it=waitQ.begin(); it!=waitQ.end();) {
        mis_addr = it->addr;
        mis_src = it->src;
        if(banks[0]->SameTagIndex(mis_addr,Q->aq.back().addr)
            && mis_src==Q->aq.back().src) {
          aq_handled = 1;
          mem_rsp++;
          MissReqHandle(mis_addr, mis_src, R);
          if (it->cmd != WB)
            L1Q[it->src-minL1]->aq.push_back(*it);
          it = waitQ.erase(it);
          // check and handle coalascing request
          CoalascingHandle(mis_addr, mis_src);
          Q->aq.pop_back();
          break;
        }
        if (!aq_handled)
          it++;
      }
    }
    if(aq_handled == 0) {
      cout<<"Error: "<<Q->aq.back().addr<<" @ "<<cur_cyc<<endl;
      cout<<"L2 AQ not handled"<<endl;
      exit(1);
    }
    //end of searching for one response
  }
  // handle all fresh requests
  bool req_hit, WQhit = 0;
  for(it=Q->oq.begin(); it!=Q->oq.end();) {
    total++;
    req_hit = FreshReqHandle(it->addr, it->src, it->cmd);
    // if hit
    if (req_hit) {
      if (it->cmd != WB)
        L1Q[it->src-minL1]->aq.push_back(*it);
      hit++;
    }
    // if miss
    else {
      miss++;
      // check if this missing is to be coalasced
      vector<QueueElement>::iterator wit;
      for(wit = waitQ.begin(); wit!= waitQ.end(); wit++) {
        if(banks[0]->SameTagIndex(wit->addr, it->addr) && wit->src == it->src) {
          WQhit = 1;
          break;
        }
      }
      // not coalasced, issue new request to L2
      if (!WQhit) {
        mem_req++;
        // if WB is a miss, it means previous req from L1 evict a L2 block and 
        // inclusion is enforced and WB is already completed.
        // So just pass it to memory
        MemQ->NewReq(it->src, it->addr, MEM_LATENCY, banks[0]->id, it->cmd);
      }
      if (it->cmd != WB)
        waitQ.push_back(*it);
      else
        wb++;
    }
    it = Q->oq.erase(it);
  }
}

L1Cache::L1Cache(int _size, int _block_size, int _latency, int _way, int _id) {
  cache = new Cache(_size, _block_size, _latency, _way, _id);
  Q = new Queue(_id);
  hit = 0;
  miss = 0;
  wb = 0;
  total = 0;
  access_time=0;
}

bool L1Cache::QEmpty() {
  return waitQ.empty() && Q->Empty();
}

void L1Cache::Update() {
  // take new request and count down
  Q->Commit_Reqs();
  Q->Countdown();
  // update outstanding request using rsp
  vector<QueueElement>::iterator it;
  unsigned long mis_addr;
  bool aq_handled;
  while(Q->aq.size() != 0) {
    aq_handled = 0;
    for(it=waitQ.begin(); it!=waitQ.end();) {
      mis_addr = it->addr;
      if(cache->SameTagIndex(mis_addr, Q->aq.back().addr)) {
        aq_handled = 1;
        MissReqHandle(mis_addr, it->cmd);
        access_time += cur_cyc - it->cyc + L1_LATENCY;
        //cout<<"L1 ID: "<<cache->id<<" received response @ "<<cur_cyc<<endl;
        it = waitQ.erase(it);
        // check and handle coalascing request
        CoalascingHandle(mis_addr);
        Q->aq.pop_back();
        break;
      }
      if (!aq_handled)
        it++;
    }
    if(aq_handled == 0) {
      cout<<"Error: "<<Q->aq.back().addr<<" @ "<<cur_cyc<<
        " cmd: "<<Q->aq.back().cmd<<endl;
      cout<<"L1 AQ not handled"<<" id: "<<cache->id<<endl;
      exit(1);
    }
    //end of searching for one response
  }
  // handle all fresh requests on that is ready
  bool req_hit, WQhit = 0;
  for(it=Q->oq.begin(); it!=Q->oq.end();) {
    total++;
    req_hit = FreshReqHandle(it->addr, it->src, it->cmd);
    // if hit
    if (req_hit) {
      access_time += L1_LATENCY;
      hit++;
    }
    // if miss
    else {
      miss++;
      // check if this missing is to be coalasced
      vector<QueueElement>::iterator wit;
      for(wit = waitQ.begin(); wit!= waitQ.end(); wit++) {
        if(cache->SameTagIndex(wit->addr, it->addr) && wit->src == it->src) {
          WQhit = 1;
          break;
        }
      }
      // not coalasced, issue new request to L2
      if (!WQhit) {
        if (multi_test)
          L2Q->NewReq(it->src, it->addr, L2_LATENCY, it->src, it->cmd);
        else
          L2Q->NewReq(it->src, it->addr, MEM_LATENCY, it->src, it->cmd);
      }
      it->cyc = cur_cyc;
      waitQ.push_back(*it);
      //cout<<"waitQ insert: "<<it->addr<<" cmd: "<<it->cmd<<" "<<WQhit<<endl;
    }
    it = Q->oq.erase(it);
  }
}

bool L1Cache::FreshReqHandle(unsigned long addr, int requester, Cmd cmd) {
  // no need to handle any other command on L1
  if (cmd == R)
    return cache->Read(addr, requester);
  else
    return cache->Write(addr, requester);
}

void L1Cache::MissReqHandle(unsigned long addr, Cmd cmd) {
  Block* new_block = cache->GetVictim(addr);
  if (new_block->valid) {
    // dettach it from L2
    QueueElement t;
    t.src = cache->id;
    t.addr = new_block->addr;
    t.delay = 0;
    t.cmd = EVICT;
    t.blk = new_block;
    L2Q->aq.push_back(t);
    // if victim is dirty, needs to writeback
    if (new_block->dirty) {
      wb++;
      L2Q->NewReq(cache->id, new_block->addr, L2_LATENCY, cache->id, WB);
      new_block->dirty = 0;
    }
  }
  // fill new_block with new data
  cache->FillBlock(addr, cmd, cache->id, new_block);
  // attach it to L2
  QueueElement t;
  t.src = cache->id;
  t.addr = new_block->addr;
  t.delay = 0;
  t.cmd = FILL;
  t.blk = new_block;
  L2Q->aq.push_back(t);
}

void L1Cache::CoalascingHandle(unsigned long addr) {
  vector<QueueElement>::iterator it;
  for(it = waitQ.begin(); it != waitQ.end();) {
    if(cache->SameTagIndex(addr, it->addr)) {// src match is guaranteed by
      access_time += cur_cyc - it->cyc + L1_LATENCY;
      bool r = FreshReqHandle(addr, cache->id, it->cmd);
      assert(r == true);
      it = waitQ.erase(it);
      if (it == waitQ.end())
        break;
    }
    else
      it++;
  }
  return;
}
/*
void L1Cache::PrintStats() {
  cout<<"=================================================="<<endl;
  cout<<"L1 ID: "<<cache->id<<endl;
  cout<<"\t Size: "<<cache->size<<" KB\n";
  cout<<"\t BlockSize: "<<cache->block_size<<" B\n";
  cout<<"\t Number of Blocks: "<<cache->block_num<<endl;
  cout<<"\t Number of Sets: "<<cache->way<<endl;
  cout<<"\t WriteBack Polic: WriteBack\n";
  cout<<"\t Latency: "<<L1_LATENCY<<"\n";
  cout<<"\t Hit: "<<hit<<endl;
  cout<<"\t Miss: "<<miss<<endl;
  cout<<"\t Write_back: "<<wb<<endl;
  cout<<"\t Total: "<<total<<endl;
  cout<<"\t Access Time: "<<access_time<<endl;
  cout<<"\t AMAT: "<<(access_time/(hit+miss))<<endl;
}
*/

void L1Cache::PrintStats() {
  double ttl=hit+miss;

  cout.setf(ios::fixed, ios::floatfield);
  cout.setf(ios::showpoint);
  cout.precision(4);

  cout<<"=================================================="<<endl;
  cout<<"Core: "<<'\t'<<cache->id<<endl;
  cout<<"L1: "<<'\t'<<(hit+miss)<<'\t'<<miss<<'\t'<<(miss/ttl)<<endl;
  cout<<"AMAT: "<<'\t'<<(access_time/ttl)<<endl;
}


Cache::Cache(int _size, int _block_size, int _latency, int _way, int _id) {
  size = _size;
  block_size = _block_size;
  latency = _latency;
  way = _way;
  id = _id;

  block_num = size * 1024 / block_size;
  blocks = new Block[block_num];

  for(int i=0; i<block_num; i++)
    blocks[i].valid = 0;
}

bool Cache::SameTagIndex(unsigned long addr1, unsigned long addr2) {
  return (GetTag(addr1)==GetTag(addr2) && GetIndex(addr1)==GetIndex(addr2));
}

int Cache::GetIndex(unsigned long addr) {
  unsigned long tag_index = addr>>log2(block_size);
  unsigned int index_mask = block_num / way -1;
  return tag_index & index_mask;
}

int Cache::GetTag(unsigned long addr) {
  unsigned long tag_index = addr>>log2(block_size);
  unsigned int row_count = block_num / way;
  return tag_index>>log2(row_count);
}

Block* Cache::findBlock(unsigned long addr, int requester) {
  unsigned int index = GetIndex(addr);
  unsigned int tag = GetTag(addr);

  Block* blk;

  for(int i=0; i<way; i++) {
    // Iterate through all blocks within a way
    blk = &blocks[index*way + i];
    if (blk->valid && blk->owner == requester && tag == blk->tag)
      return blk;
  }
  return NULL;
}

bool Cache::Read(unsigned long addr, int requester) {
  Block* blk = findBlock(addr, requester);
  if (blk != NULL) {
    blk->last_cyc = cur_cyc;
    return 1; // Hit!
  }
  else {
    return 0; // Miss!
  }
}

bool Cache::Write(unsigned long addr, int requester) {
  Block* blk = findBlock(addr, requester);
  if (blk != NULL) {
    blk->last_cyc = cur_cyc;
    blk->dirty = 1;
    return 1; // Hit!
  }
  else {
    return 0; // Miss!
  }
}

Block* Cache::GetVictim(unsigned long addr) {
  unsigned int index = GetIndex(addr);
  unsigned int tag = GetTag(addr);
  Block* blk;

  unsigned long LRU_cyc = cur_cyc;
  Block* LRU_blk;

  //dprint("index: %d, tag: %d", index, tag);

  for(int i=0; i<way; i++) {
    // Iterate through all blocks within a way
    blk = &blocks[index*way + i];
    if (blk->valid == 0)
      return blk;
    else if (LRU_cyc > blk->last_cyc) {
      LRU_cyc = blk->last_cyc;
      LRU_blk = blk;
    }
  }
  return LRU_blk;
}

void Cache::FillBlock(unsigned long addr, Cmd cmd, int requester, Block* block) {
  block->valid = 1;
  block->dirty = ((cmd==W) | (cmd==WB));
  block->tag = GetTag(addr);
  block->owner = requester;
  block->last_cyc = cur_cyc;
  block->addr = addr;
}
